package 剑指offer_专项突破版;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * 剑指 Offer II 074. 合并区间
 */
public class Num74 {
    public int[][] merge(int[][] intervals) {
        //关于每一组第一个元素排序
        Arrays.sort(intervals,(i1, i2) -> i1[0] - i2[0]);
        //保存最终合并好的数组
        List<int[]> merged = new LinkedList<>();
        int i = 0;
        while (i < intervals.length){
            int[] temp = new int[]{
                    intervals[i][0], intervals[i][1]
            };
            int j = i + 1;
            while (j < intervals.length && intervals[j][0] <= temp[1]){
                temp[1] = Math.max(temp[1], intervals[j][1]);
                j ++;
            }
            merged.add(temp);
            i = j;
        }
        int[][] result = new int[merged.size()][];
        return merged.toArray(result);
    }
}
